package cn.com.mdx.sort.heapsort.sliderpuzzle;

import cn.com.mdx.sort.SortUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * <p> 面板类
 *
 * @author ：huangy
 * @date ：Created in 2020/11/3 10:13 上午
 */
public class Board implements Comparable<Board> {

    /**
     * 面板边长
     */
    private int N;

    /**
     * n x n的二维数组
     */
    private Integer[][] tiles;

    /**
     * 移之前0的x坐标
     */
    private int beforeZeroX = -1;

    /**
     * 移之前0y坐标
     */
    private int beforeZeroY = -1;

    /**
     * 面板移动的次数
     */
    private int move = 0;

    /**
     * @param tiles 包含nxn个数字的二维数组
     * @Author huangy
     * @description //TODO 创建一个有n x n个滑块的面板tiles[row][col]表示在(row, col)位置的滑块
     * @date 3:24 下午 2020/11/5
     **/
    public Board(Integer[][] tiles) {
        if (tiles != null && tiles.length > 0) {
            N = tiles.length;
            this.tiles = tiles;
        }
    }

    /**
     * @return java.lang.String
     * @Author huangy
     * @description //TODO 面板转字符串方法
     * @date 5:24 下午 2020/11/5
     **/
    public String toString() {
        if (tiles != null && tiles.length > 0) {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append(N).append("\n");
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    stringBuilder.append(tiles[i][j]);
                    if (j != N - 1) stringBuilder.append(",");
                }
                stringBuilder.append("\n");
            }
            return stringBuilder.toString();
        }
        return "";
    }

    /**
     * @return int
     * @Author huangy
     * @description //TODO 面板尺寸
     * @date 5:26 下午 2020/11/5
     **/
    public int dimension() {
        return N;
    }

    /**
     * @return int
     * @Author huangy
     * @description //TODO 汉明距离：不在正确位置的滑块数量
     * @date 5:29 下午 2020/11/5
     **/
    public int hamming() {
        int wrongPosNum = 0;
        if (tiles != null && tiles.length > 0) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (tiles[i][j] != N * i + j + 1) wrongPosNum++;
                }
            }
        }
        return wrongPosNum;
    }

    /**
     * @return int
     * @Author huangy
     * @description //TODO 滑块与目标面板的曼哈顿距离之和(垂直和水平距离)
     * @date 5:32 下午 2020/11/5
     **/
    public int manhattan() {
        int manhattanDistance = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (tiles[i][j] == 0) continue;
                //通过对应值与面板大小相除的余数和商，计算滑块应该在的正确位置
                int horizontalDistance = tiles[i][j] % N;
                int verticalDistance = tiles[i][j] / N;
                if (horizontalDistance == 0) {
                    horizontalDistance = N - 1;
                    verticalDistance = verticalDistance - 1;
                } else horizontalDistance -= 1;
                //计算当前离正确列位置的距离
                horizontalDistance = Math.abs(horizontalDistance - j);
                //计算滑块离正确行位置的距离
                verticalDistance = Math.abs(verticalDistance - i);
                manhattanDistance = manhattanDistance + horizontalDistance + verticalDistance;
            }
        }
        return manhattanDistance;
    }

    /**
     * @return boolean false 不是 true 是
     * @Author huangy
     * @description //TODO 判断当前面板是否已经是目标面板
     * @date 5:33 下午 2020/11/5
     **/
    public boolean isGoal() {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (tiles[i][j] != N * i + j + 1) return false;
        return true;
    }

    /**
     * @param other 其他面板
     * @return boolean false 不相等 true 相等
     * @Author huangy
     * @description //TODO 判断两个面板是否相等
     * @date 5:36 下午 2020/11/5
     **/
    public boolean equals(Object other) {
        if (other instanceof Board) {
            Board otherBoard = (Board) other;
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++) if (!tiles[i][j].equals(otherBoard.tiles[i][j])) return false;
            return true;
        }
        return false;
    }

    /**
     * @return Board 交换滑块后的面板
     * @Author huangy
     * @description //TODO 通过交换任意一对滑块获得的面板
     * @date 5:37 下午 2020/11/5
     **/
    public Board twin() {
        Random random = new Random();
        int randomRow1 = random.nextInt(N);
        int randomCol1 = random.nextInt(N);
        int randomRow2 = random.nextInt(N);
        int randomCol2 = random.nextInt(N);
        int temp = this.tiles[randomRow1][randomCol1];
        this.tiles[randomRow1][randomCol1] = this.tiles[randomRow2][randomCol2];
        this.tiles[randomRow2][randomCol2] = temp;
        return this;
    }

    /**
     * @return java.lang.Iterable<cn.com.mdx.sort.heapsort.sliderpuzzle.Board>
     * @Author huangy
     * @description //TODO 相邻面板
     * @date 6:03 下午 2020/11/6
     **/
    public Iterable<Board> neighbors() {
        List<Board> boardList = new ArrayList<>();
        //获取空白格的位置
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                if (tiles[i][j] == 0) {
                    if (i - 1 >= 0) addNeighbor(boardList, i, j, i - 1, j);
                    if (i + 1 < N) addNeighbor(boardList, i, j, i + 1, j);
                    if (j - 1 >= 0) addNeighbor(boardList, i, j, i, j - 1);
                    if (j + 1 < N) addNeighbor(boardList, i, j, i, j + 1);
                }
        return boardList;
    }

    /**
     * @param boardList 面板集合
     * @param row1      第一个行坐标
     * @param column1   第一个列坐标
     * @param row2      第二个行坐标
     * @param column2   弟二哥列坐标
     * @return void
     * @Author huangy
     * @description //TODO
     * @date 10:36 下午 2020/11/8
     **/
    private void addNeighbor(List<Board> boardList, int row1, int column1, int row2, int column2) {
        //复制原来的面板
        Integer[][] tilesCopy = copayArray(tiles);
        SortUtils.exChange(tilesCopy, row1, column1, row2, column2);
        if (row2 == beforeZeroX && column2 == beforeZeroY) return;
        Board newBoard = new Board(tilesCopy);
        newBoard.beforeZeroX = row1;
        newBoard.beforeZeroY = column1;
        newBoard.move = this.move + 1;
        //添加
        boardList.add(newBoard);
    }

    /**
     * @return int
     * @Author huangy
     * @description //TODO 获取面板到初始面板移动的次数
     * @date 3:46 下午 2020/11/27
     **/
    public int getMove() {
        return move;
    }

    @Override
    public int compareTo(Board that) {
        return this.manhattan() + this.move - that.manhattan() - that.move;
    }

    public static void main(String[] args) {
        Integer[][] array = initTiles(3);
        Board board = new Board(array);
        System.out.println(board);
        System.out.println("曼哈顿距离：" + board.manhattan());
    }

    /**
     * @return Integer[][] 二维数组
     * @date 5:41 下午 2020/11/5
     **/
    public static Integer[][] initTiles(int n) {
        Integer[][] array = new Integer[n][n];
        if (n > 0) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    array[i][j] = n * i + j;
                }
            }
        }
        return array;
    }

    private Integer[][] copayArray(Integer[][] origArray) {
        Integer[][] copyArray = new Integer[origArray.length][origArray.length];
        for (int i = 0; i < origArray.length; i++) {
            System.arraycopy(origArray[i], 0, copyArray[i], 0, origArray.length);
        }
        return copyArray;
    }

}
